
<!DOCTYPE html>

<html>
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>pymatgen.optimization.linear_assignment_numpy &#8212; pymatgen 2020.7.3 documentation</title>
    <link rel="stylesheet" href="../../../_static/basic.css" type="text/css" />
    <link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
    <script id="documentation_options" data-url_root="../../../" src="../../../_static/documentation_options.js"></script>
    <script src="../../../_static/jquery.js"></script>
    <script src="../../../_static/underscore.js"></script>
    <script src="../../../_static/doctools.js"></script>
    <script src="../../../_static/language_data.js"></script>
    <script async="async" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
    <link rel="index" title="Index" href="../../../genindex.html" />
    <link rel="search" title="Search" href="../../../search.html" />
 
<script type="text/javascript">
  var _gaq = _gaq || [];
  _gaq.push(['_setAccount', 'UA-33990148-1']);
  _gaq.push(['_trackPageview']);
</script>

  </head><body>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">pymatgen 2020.7.3 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" >Module code</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="../../pymatgen.html" accesskey="U">pymatgen</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="">pymatgen.optimization.linear_assignment_numpy</a></li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
          <div class="body" role="main">
            
  <h1>Source code for pymatgen.optimization.linear_assignment_numpy</h1><div class="highlight"><pre>
<span></span><span class="c1"># coding: utf-8</span>
<span class="c1"># Copyright (c) Pymatgen Development Team.</span>
<span class="c1"># Distributed under the terms of the MIT License.</span>


<span class="sd">&quot;&quot;&quot;</span>
<span class="sd">This module contains an algorithm to solve the Linear Assignment Problem.</span>
<span class="sd">It has the same functionality as linear_assignment.pyx, but is much slower</span>
<span class="sd">as it is vectorized in numpy rather than cython</span>
<span class="sd">&quot;&quot;&quot;</span>

<span class="n">__author__</span> <span class="o">=</span> <span class="s2">&quot;Will Richards&quot;</span>
<span class="n">__copyright__</span> <span class="o">=</span> <span class="s2">&quot;Copyright 2011, The Materials Project&quot;</span>
<span class="n">__version__</span> <span class="o">=</span> <span class="s2">&quot;1.0&quot;</span>
<span class="n">__maintainer__</span> <span class="o">=</span> <span class="s2">&quot;Will Richards&quot;</span>
<span class="n">__email__</span> <span class="o">=</span> <span class="s2">&quot;wrichards@mit.edu&quot;</span>
<span class="n">__date__</span> <span class="o">=</span> <span class="s2">&quot;Jan 28, 2013&quot;</span>

<span class="kn">import</span> <span class="nn">numpy</span> <span class="k">as</span> <span class="nn">np</span>


<div class="viewcode-block" id="LinearAssignment"><a class="viewcode-back" href="../../../pymatgen.optimization.linear_assignment_numpy.html#pymatgen.optimization.linear_assignment_numpy.LinearAssignment">[docs]</a><span class="k">class</span> <span class="nc">LinearAssignment</span><span class="p">:</span>
    <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    This class finds the solution to the Linear Assignment Problem.</span>
<span class="sd">    It finds a minimum cost matching between two sets, given a cost</span>
<span class="sd">    matrix.</span>

<span class="sd">    This class is an implementation of the LAPJV algorithm described in:</span>
<span class="sd">    R. Jonker, A. Volgenant. A Shortest Augmenting Path Algorithm for</span>
<span class="sd">    Dense and Sparse Linear Assignment Problems. Computing 38, 325-340</span>
<span class="sd">    (1987)</span>

<span class="sd">    .. attribute: min_cost:</span>

<span class="sd">        The minimum cost of the matching</span>

<span class="sd">    .. attribute: solution:</span>

<span class="sd">        The matching of the rows to columns. i.e solution = [1, 2, 0]</span>
<span class="sd">        would match row 0 to column 1, row 1 to column 2 and row 2</span>
<span class="sd">        to column 0. Total cost would be c[0, 1] + c[1, 2] + c[2, 0]</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">costs</span><span class="p">,</span> <span class="n">epsilon</span><span class="o">=</span><span class="mf">1e-6</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Args:</span>
<span class="sd">            costs: The cost matrix of the problem. cost[i,j] should be the</span>
<span class="sd">                cost of matching x[i] to y[j]. The cost matrix may be</span>
<span class="sd">                rectangular</span>
<span class="sd">            epsilon: Tolerance for determining if solution vector is &lt; 0</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">orig_c</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">array</span><span class="p">(</span><span class="n">costs</span><span class="p">,</span> <span class="n">dtype</span><span class="o">=</span><span class="n">np</span><span class="o">.</span><span class="n">float64</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">nx</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">ny</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">orig_c</span><span class="o">.</span><span class="n">shape</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">n</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">ny</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_inds</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">arange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">n</span><span class="p">)</span>

        <span class="bp">self</span><span class="o">.</span><span class="n">epsilon</span> <span class="o">=</span> <span class="nb">abs</span><span class="p">(</span><span class="n">epsilon</span><span class="p">)</span>

        <span class="c1"># check that cost matrix is square</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">nx</span> <span class="o">&gt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">ny</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s2">&quot;cost matrix must have at least as many columns as rows&quot;</span><span class="p">)</span>

        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">nx</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">ny</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">c</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">orig_c</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="c1"># Can run into precision issues if np.max is used as the fill value (since a</span>
            <span class="c1"># value of this size doesn&#39;t necessarily end up in the solution). A value</span>
            <span class="c1"># at least as large as the maximin is, however, guaranteed to appear so it</span>
            <span class="c1"># is a safer choice. The fill value is not zero to avoid choosing the extra</span>
            <span class="c1"># rows in the initial column reduction step</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">c</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">full</span><span class="p">((</span><span class="bp">self</span><span class="o">.</span><span class="n">n</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">n</span><span class="p">),</span> <span class="n">np</span><span class="o">.</span><span class="n">max</span><span class="p">(</span><span class="n">np</span><span class="o">.</span><span class="n">min</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">orig_c</span><span class="p">,</span> <span class="n">axis</span><span class="o">=</span><span class="mi">1</span><span class="p">)))</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">c</span><span class="p">[:</span><span class="bp">self</span><span class="o">.</span><span class="n">nx</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">orig_c</span>

        <span class="c1"># initialize solution vectors</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_x</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">zeros</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">n</span><span class="p">,</span> <span class="n">dtype</span><span class="o">=</span><span class="n">np</span><span class="o">.</span><span class="n">int</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_y</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>

        <span class="c1"># if column reduction doesn&#39;t find a solution, augment with shortest</span>
        <span class="c1"># paths until one is found</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_column_reduction</span><span class="p">():</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_augmenting_row_reduction</span><span class="p">()</span>
            <span class="c1"># initialize the reduced costs</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_update_cred</span><span class="p">()</span>
            <span class="k">while</span> <span class="o">-</span><span class="mi">1</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">_augment</span><span class="p">()</span>

        <span class="bp">self</span><span class="o">.</span><span class="n">solution</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">[:</span><span class="bp">self</span><span class="o">.</span><span class="n">nx</span><span class="p">]</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_min_cost</span> <span class="o">=</span> <span class="kc">None</span>

    <span class="nd">@property</span>
    <span class="k">def</span> <span class="nf">min_cost</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Returns the cost of the best assignment</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_min_cost</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_min_cost</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_min_cost</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">sum</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">c</span><span class="p">[</span><span class="n">np</span><span class="o">.</span><span class="n">arange</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">nx</span><span class="p">),</span> <span class="bp">self</span><span class="o">.</span><span class="n">solution</span><span class="p">])</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_min_cost</span>

    <span class="k">def</span> <span class="nf">_column_reduction</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Column reduction and reduction transfer steps from LAPJV algorithm</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c1"># assign each column to its lowest cost row, ensuring that only row</span>
        <span class="c1"># or column is assigned once</span>
        <span class="n">i1</span><span class="p">,</span> <span class="n">j</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">unique</span><span class="p">(</span><span class="n">np</span><span class="o">.</span><span class="n">argmin</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">c</span><span class="p">,</span> <span class="n">axis</span><span class="o">=</span><span class="mi">0</span><span class="p">),</span> <span class="n">return_index</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">[</span><span class="n">i1</span><span class="p">]</span> <span class="o">=</span> <span class="n">j</span>

        <span class="c1"># if problem is solved, return</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">i1</span><span class="p">)</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">n</span><span class="p">:</span>
            <span class="k">return</span> <span class="kc">False</span>

        <span class="bp">self</span><span class="o">.</span><span class="n">_y</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">i1</span>

        <span class="c1"># reduction_transfer</span>
        <span class="c1"># tempc is array with previously assigned matchings masked</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_v</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">min</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">c</span><span class="p">,</span> <span class="n">axis</span><span class="o">=</span><span class="mi">0</span><span class="p">)</span>
        <span class="n">tempc</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">c</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>
        <span class="n">tempc</span><span class="p">[</span><span class="n">i1</span><span class="p">,</span> <span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">inf</span>
        <span class="n">mu</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">min</span><span class="p">(</span><span class="n">tempc</span><span class="p">[</span><span class="n">i1</span><span class="p">,</span> <span class="p">:]</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">_v</span><span class="p">[</span><span class="kc">None</span><span class="p">,</span> <span class="p">:],</span> <span class="n">axis</span><span class="o">=</span><span class="mi">1</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_v</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">-=</span> <span class="n">mu</span>
        <span class="k">return</span> <span class="kc">True</span>

    <span class="k">def</span> <span class="nf">_augmenting_row_reduction</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Augmenting row reduction step from LAPJV algorithm</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">unassigned</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">where</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_x</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">)[</span><span class="mi">0</span><span class="p">]</span>
        <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">unassigned</span><span class="p">:</span>
            <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">c</span><span class="o">.</span><span class="n">size</span><span class="p">):</span>
                <span class="c1"># Time in this loop can be proportional to 1/epsilon</span>
                <span class="c1"># This step is not strictly necessary, so cutoff early</span>
                <span class="c1"># to avoid near-infinite loops</span>

                <span class="c1"># find smallest 2 values and indices</span>
                <span class="n">temp</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">_v</span>
                <span class="n">j1</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">argmin</span><span class="p">(</span><span class="n">temp</span><span class="p">)</span>
                <span class="n">u1</span> <span class="o">=</span> <span class="n">temp</span><span class="p">[</span><span class="n">j1</span><span class="p">]</span>
                <span class="n">temp</span><span class="p">[</span><span class="n">j1</span><span class="p">]</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">inf</span>
                <span class="n">j2</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">argmin</span><span class="p">(</span><span class="n">temp</span><span class="p">)</span>
                <span class="n">u2</span> <span class="o">=</span> <span class="n">temp</span><span class="p">[</span><span class="n">j2</span><span class="p">]</span>

                <span class="k">if</span> <span class="n">u1</span> <span class="o">&lt;</span> <span class="n">u2</span><span class="p">:</span>
                    <span class="bp">self</span><span class="o">.</span><span class="n">_v</span><span class="p">[</span><span class="n">j1</span><span class="p">]</span> <span class="o">-=</span> <span class="n">u2</span> <span class="o">-</span> <span class="n">u1</span>
                <span class="k">elif</span> <span class="bp">self</span><span class="o">.</span><span class="n">_y</span><span class="p">[</span><span class="n">j1</span><span class="p">]</span> <span class="o">!=</span> <span class="o">-</span><span class="mi">1</span><span class="p">:</span>
                    <span class="n">j1</span> <span class="o">=</span> <span class="n">j2</span>
                <span class="n">k</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_y</span><span class="p">[</span><span class="n">j1</span><span class="p">]</span>
                <span class="k">if</span> <span class="n">k</span> <span class="o">!=</span> <span class="o">-</span><span class="mi">1</span><span class="p">:</span>
                    <span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span>
                    <span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">j1</span>
                    <span class="bp">self</span><span class="o">.</span><span class="n">_y</span><span class="p">[</span><span class="n">j1</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span>
                    <span class="n">i</span> <span class="o">=</span> <span class="n">k</span>
                <span class="k">if</span> <span class="n">k</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="ow">or</span> <span class="nb">abs</span><span class="p">(</span><span class="n">u1</span> <span class="o">-</span> <span class="n">u2</span><span class="p">)</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">epsilon</span><span class="p">:</span>
                    <span class="k">break</span>

    <span class="k">def</span> <span class="nf">_update_cred</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Updates the reduced costs with the values from the</span>
<span class="sd">        dual solution</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">ui</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">c</span><span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">_inds</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">]</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">_v</span><span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">]</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">cred</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">c</span> <span class="o">-</span> <span class="n">ui</span><span class="p">[:,</span> <span class="kc">None</span><span class="p">]</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">_v</span><span class="p">[</span><span class="kc">None</span><span class="p">,</span> <span class="p">:]</span>

    <span class="k">def</span> <span class="nf">_augment</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Finds a minimum cost path and adds it to the matching</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c1"># build a minimum cost tree</span>
        <span class="n">_pred</span><span class="p">,</span> <span class="n">_ready</span><span class="p">,</span> <span class="n">istar</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">mu</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_build_tree</span><span class="p">()</span>

        <span class="c1"># update prices</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_v</span><span class="p">[</span><span class="n">_ready</span><span class="p">]</span> <span class="o">+=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_d</span><span class="p">[</span><span class="n">_ready</span><span class="p">]</span> <span class="o">-</span> <span class="n">mu</span>

        <span class="c1"># augment the solution with the minimum cost path from the</span>
        <span class="c1"># tree. Follows an alternating path along matched, unmatched</span>
        <span class="c1"># edges from X to Y</span>
        <span class="k">while</span> <span class="kc">True</span><span class="p">:</span>
            <span class="n">i</span> <span class="o">=</span> <span class="n">_pred</span><span class="p">[</span><span class="n">j</span><span class="p">]</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_y</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span>
            <span class="n">k</span> <span class="o">=</span> <span class="n">j</span>
            <span class="n">j</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">k</span>
            <span class="k">if</span> <span class="n">i</span> <span class="o">==</span> <span class="n">istar</span><span class="p">:</span>
                <span class="k">break</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_update_cred</span><span class="p">()</span>

    <span class="k">def</span> <span class="nf">_build_tree</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Builds the tree finding an augmenting path. Alternates along</span>
<span class="sd">        matched and unmatched edges between X and Y. The paths are</span>
<span class="sd">        stored in _pred (new predecessor of nodes in Y), and</span>
<span class="sd">        self._x and self._y</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="c1"># find unassigned i*</span>
        <span class="n">istar</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">argmin</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_x</span><span class="p">)</span>

        <span class="c1"># compute distances</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_d</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">c</span><span class="p">[</span><span class="n">istar</span><span class="p">]</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">_v</span>
        <span class="n">_pred</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">zeros</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">n</span><span class="p">,</span> <span class="n">dtype</span><span class="o">=</span><span class="n">np</span><span class="o">.</span><span class="n">int</span><span class="p">)</span> <span class="o">+</span> <span class="n">istar</span>

        <span class="c1"># initialize sets</span>
        <span class="c1"># READY: set of nodes visited and in the path (whose price gets</span>
        <span class="c1"># updated in augment)</span>
        <span class="c1"># SCAN: set of nodes at the bottom of the tree, which we need to</span>
        <span class="c1"># look at</span>
        <span class="c1"># T0DO: unvisited nodes</span>
        <span class="n">_ready</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">zeros</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">n</span><span class="p">,</span> <span class="n">dtype</span><span class="o">=</span><span class="n">np</span><span class="o">.</span><span class="n">bool</span><span class="p">)</span>
        <span class="n">_scan</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">zeros</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">n</span><span class="p">,</span> <span class="n">dtype</span><span class="o">=</span><span class="n">np</span><span class="o">.</span><span class="n">bool</span><span class="p">)</span>
        <span class="n">_todo</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">zeros</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">n</span><span class="p">,</span> <span class="n">dtype</span><span class="o">=</span><span class="n">np</span><span class="o">.</span><span class="n">bool</span><span class="p">)</span> <span class="o">+</span> <span class="kc">True</span>

        <span class="k">while</span> <span class="kc">True</span><span class="p">:</span>
            <span class="c1"># populate scan with minimum reduced distances</span>
            <span class="k">if</span> <span class="kc">True</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">_scan</span><span class="p">:</span>
                <span class="n">mu</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">min</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_d</span><span class="p">[</span><span class="n">_todo</span><span class="p">])</span>
                <span class="n">_scan</span><span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">_d</span> <span class="o">==</span> <span class="n">mu</span><span class="p">]</span> <span class="o">=</span> <span class="kc">True</span>
                <span class="n">_todo</span><span class="p">[</span><span class="n">_scan</span><span class="p">]</span> <span class="o">=</span> <span class="kc">False</span>
                <span class="n">j</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">argmin</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_y</span> <span class="o">*</span> <span class="n">_scan</span><span class="p">)</span>
                <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_y</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="ow">and</span> <span class="n">_scan</span><span class="p">[</span><span class="n">j</span><span class="p">]:</span>
                    <span class="k">return</span> <span class="n">_pred</span><span class="p">,</span> <span class="n">_ready</span><span class="p">,</span> <span class="n">istar</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">mu</span>

            <span class="c1"># pick jstar from scan (scan always has at least 1)</span>
            <span class="n">_jstar</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">argmax</span><span class="p">(</span><span class="n">_scan</span><span class="p">)</span>

            <span class="c1"># pick i associated with jstar</span>
            <span class="n">i</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_y</span><span class="p">[</span><span class="n">_jstar</span><span class="p">]</span>

            <span class="n">_scan</span><span class="p">[</span><span class="n">_jstar</span><span class="p">]</span> <span class="o">=</span> <span class="kc">False</span>
            <span class="n">_ready</span><span class="p">[</span><span class="n">_jstar</span><span class="p">]</span> <span class="o">=</span> <span class="kc">True</span>

            <span class="c1"># find shorter distances</span>
            <span class="n">newdists</span> <span class="o">=</span> <span class="n">mu</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">cred</span><span class="p">[</span><span class="n">i</span><span class="p">,</span> <span class="p">:]</span>
            <span class="n">shorter</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">logical_and</span><span class="p">(</span><span class="n">newdists</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">_d</span><span class="p">,</span> <span class="n">_todo</span><span class="p">)</span>

            <span class="c1"># update distances</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_d</span><span class="p">[</span><span class="n">shorter</span><span class="p">]</span> <span class="o">=</span> <span class="n">newdists</span><span class="p">[</span><span class="n">shorter</span><span class="p">]</span>

            <span class="c1"># update predecessors</span>
            <span class="n">_pred</span><span class="p">[</span><span class="n">shorter</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span>

            <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="n">np</span><span class="o">.</span><span class="n">nonzero</span><span class="p">(</span><span class="n">np</span><span class="o">.</span><span class="n">logical_and</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_d</span> <span class="o">==</span> <span class="n">mu</span><span class="p">,</span> <span class="n">_todo</span><span class="p">))[</span><span class="mi">0</span><span class="p">]:</span>
                <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_y</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">:</span>
                    <span class="k">return</span> <span class="n">_pred</span><span class="p">,</span> <span class="n">_ready</span><span class="p">,</span> <span class="n">istar</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">mu</span>
                <span class="n">_scan</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="kc">True</span>
                <span class="n">_todo</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="kc">False</span></div>
</pre></div>

            <div class="clearer"></div>
          </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../../index.html">pymatgen 2020.7.3 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../../index.html" >Module code</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="../../pymatgen.html" >pymatgen</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="">pymatgen.optimization.linear_assignment_numpy</a></li> 
      </ul>
    </div>

    <div class="footer" role="contentinfo">
        &#169; Copyright 2011, Pymatgen Development Team.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 3.1.2.
    </div>
<div class="footer">This page uses <a href="http://analytics.google.com/">
Google Analytics</a> to collect statistics. You can disable it by blocking
the JavaScript coming from www.google-analytics.com.
<script type="text/javascript">
  (function() {
    var ga = document.createElement('script');
    ga.src = ('https:' == document.location.protocol ?
              'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
    ga.setAttribute('async', 'true');
    document.documentElement.firstChild.appendChild(ga);
  })();
</script>
</div>

  </body>
</html>